#include <stdio.h>
#include <string.h>
#include <math.h>
#define M 200000
int main()
{
	int a[M] = {0};
	int i, j, t, n;
	int x=10000000+9;
	int cc = 0;
	int all[1000];
	// printf("%d", x);
	while(scanf("%d", &n) != EOF)
	{
		t = 0;
		for(i = 0; i < n; i++)
		{
			scanf("%d", &a[i]);
		}
		for(i = 1; i < n; i++)
		{
			for(j = i-1; j >= 0; j--)
				if(a[i] > a[j]) t++;
		}
		t = t % x;
		all[cc] = t;
		cc++;
		// memset(a,0,sizeof(a));
	}
	for (i = 0; i < cc; i++)
		printf("%d\n", all[i]);
	return 0;
}
